#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <string.h>
#include "graphe.h"



Graphe nouveauGraphe(const int nbNoeuds)
{
	Graphe g;
	int i;

	g.noeuds = (Noeud*) malloc (nbNoeuds * sizeof(Noeud));
	g.nbN = nbNoeuds;
	for(i=0;i<nbNoeuds;i++)
	{
		g.noeuds[i] = nouveauNoeud("",0,0,i);
	}

	g.importants = NULL;
	g.nbI = 0;

	g.nbP = (nbNoeuds*(nbNoeuds-1))/2;
	g.poids = (Arete*) malloc ((g.nbP)*sizeof(Arete));
	for(i=0;i<(g.nbP);i++)
	{
		g.poids[i] = nouvelleArete(NULL,0,0);
	}

	return g;
}


void testamentGraphe(Graphe* g)
{
	int i;

	for(i=0;i<g->nbP;i++)
	{
		testamentArete(&((g->poids)[i]));
	}

	if(g->poids != NULL)
	{ free(g->poids); }
	if(g->importants != NULL)
	free(g->importants);
	if(g->noeuds != NULL)
	free(g->noeuds);

	g->nbN = 0;
	g->nbP = 0;
	g->nbI = 0;
	g->noeuds = NULL;
	g->poids = NULL;
	g->importants = NULL;
}


Graphe nouveauGrapheFichier1(const char* nomFichier)
{
	Graphe g;
	FILE* f;
	Noeud** chemin;
	int i, nbN, nbA, nbI, n1, n2, poids;

	f = fopen(nomFichier,"r");
	fscanf(f, "%d %d \n",&nbN,&nbA);

	g = nouveauGraphe(nbN);

	for(i=0;i<nbA;i++)
	{
		fscanf(f, "%d %d %d \n", &n1, &n2, &poids);
		if (n1>n2) /* swap */
		{
			n2 = n1+n2;
			n1 = n2-n1;
			n2 = n2-n1;
		}

		chemin = (Noeud**) malloc(2*sizeof(Noeud*));
		chemin[0] = &(g.noeuds[n1-1]);
		chemin[1] = &(g.noeuds[n2-1]);

		g.poids[((nbN-1)*(nbN)/2) - ((nbN-n1)*(nbN-n1+1)/2) + (n2-n1) - 1] = nouvelleArete(chemin,2,poids);
	}

	fscanf(f, "%d \n", &nbI);

	g.nbI = nbI;
	g.importants = (Noeud**) malloc (nbI*sizeof(Noeud*));
	for(i=0;i<nbI;i++)
	{
		fscanf(f, "%d ", &n1);
		g.importants[i] = &(g.noeuds[n1-1]);
	}

	fclose(f);

	return g;
}


Graphe nouveauGrapheFichier2(const char* nomFichier)
{
	Graphe g;
	FILE* f;
	Noeud** chemin;
	char nom[50];
	int i;
	int nbN, nbA, nbI;
	int n1, n2, posX, posY, poids;

	f = fopen(nomFichier,"r");
	fscanf(f, "%d\n",&nbN);

	g = nouveauGraphe(nbN);

	for(i=0;i<nbN;i++)
	{
		fscanf(f, "%d %d %50s\n", &posX, &posY, nom);
		(g.noeuds)[i] = nouveauNoeud(nom, posX, posY, i);
	}


	fscanf(f, "\n%d\n", &nbA);

	for(i=0;i<nbA;i++)
	{
		fscanf(f, "%d %d %d \n", &n1, &n2, &poids);

		if (n1>n2) /* swap */
		{
			n2 = n1+n2;
			n1 = n2-n1;
			n2 = n2-n1;
		}

		chemin = (Noeud**) malloc(2*sizeof(Noeud*));
		chemin[0] = &(g.noeuds[n1-1]);
		chemin[1] = &(g.noeuds[n2-1]);

		g.poids[((nbN-1)*(nbN)/2) - ((nbN-n1)*(nbN-n1+1)/2) + (n2-n1) - 1] = nouvelleArete(chemin,2,poids);
	}


	fscanf(f, "\n%d\n", &nbI);
	g.nbI = nbI;
	g.importants = (Noeud**) malloc (nbI*sizeof(Noeud*));

	for(i=0;i<nbI;i++)
	{
		fscanf(f, "%d ", &n1);
		(g.importants)[i] = &(g.noeuds[n1-1]);
	}

	fclose(f);

	return g;
}



int getNbNGraphe(const Graphe* g)
{
	return g->nbN;
}


int getNbPGraphe(const Graphe* g)
{
	return g->nbP;
}


int getNbIGraphe(const Graphe* g)
{
	return g->nbI;
}


int getIndiceImportant(const Graphe* g, const int i)
{
	assert(i<(g->nbI));

	return (int)(((g->importants)[i])-(g->noeuds));
}


Noeud getINoeud(const Graphe* g, const int i)
{
	assert(i<(g->nbN));

	return (g->noeuds)[i];
}


Arete getAreteNoeuds(const Graphe* g, int n1, int n2)
{
	assert(n1 != n2);

	if (n1>n2) /* swap */
	{
		n2 = n1+n2;
		n1 = n2-n1;
		n2 = n2-n1;
	}

	return (g->poids)[(((g->nbN-1)*(g->nbN))/2) - (((g->nbN-n1-1)*(g->nbN-n1))/2) + (n2-n1) - 1];	
}


void setAreteNoeuds(Graphe* g, int n1, int n2, const Arete a)
{
	assert(n1 != n2);

	if (n1>n2) /* swap */
	{
		n2 = n1+n2;
		n1 = n2-n1;
		n2 = n2-n1;
	}

	testamentArete(&((g->poids)[(((g->nbN-1)*(g->nbN))/2) - (((g->nbN-n1-1)*(g->nbN-n1))/2) + (n2-n1) - 1]));
	(g->poids)[(((g->nbN-1)*(g->nbN))/2) - (((g->nbN-n1-1)*(g->nbN-n1))/2) + (n2-n1) - 1] = a;
}


void setCoordonneesINoeudGraphe(Graphe* g, const int i, const int posX, const int posY)
{
	assert(i<(g->nbN));

	setPosXNoeud(&((g->noeuds)[i]),posX);
	setPosYNoeud(&((g->noeuds)[i]),posY);
}



void completerEuclide(Graphe* g)
{
	int i, j, k, l;
	Arete ainit, afin;
	Noeud** chemin;

	for(i=0;i<(g->nbI);i++)
	{
		for(j=i+1;j<(g->nbI);j++)
		{
			k = getIndiceImportant(g,i);
			l = getIndiceImportant(g,j);
			ainit = getAreteNoeuds(g,k,l);

			if (getLongueurArete(&ainit) == 0)
			{
				chemin = (Noeud**) malloc (2*sizeof(Noeud*));
				chemin[0] = &(g->noeuds[k]);
				chemin[1] = &(g->noeuds[l]);
				afin = nouvelleArete(chemin, 2, distEuclide(&(g->noeuds[k]),&(g->noeuds[l])));

				setAreteNoeuds(g,k,l,afin);
			}
		}
	}
}


/* Donne un poids "infini" valable pour le graphe g, ici la somme des
   poids de toutes les arêtes plus 1 */
/* Sert à PCC */
static int infiniPoidsGraphe(const Graphe* g)
{
	int i, infini;

	infini = 0;
	for(i=0;i<(g->nbP);i++)
	{
		infini += getPoidsArete(&(g->poids[i]));
	}

	return infini+1;
}


/* "Plus Court Chemin" : Algorithme de Dijkstra */
Arete PCC(Graphe* g, const int n1, const int n2)
{
	/* VARIABLES */
	Arete res, a;
	Arete* Sommets; /* Tableau de travail des sommets du graphe*/ 
	int i, infini, lg;
	int nbNoirs, nbGris, nbBlancs;
	int pmin, grismin;
	Noeud** chemin;
	Noeud* pred;

	/* On réutilise la structure Arete pour stocker les sommets ;
	   où chemin[0] est un pointeur vers le sommet,
          chemin[1] est le prédecesseur du sommet,
		  longueur vaut 0, 1 ou 2 selon que le sommet est "noir", "gris" ou "blanc",
		  poids vaut la distance entre ce sommet et le sommet de départ. */

	infini = infiniPoidsGraphe(g);

	Sommets = (Arete*) malloc ((g->nbN)*sizeof(Arete));

	/* INITIALISATIONS */
	/* Au début, tous les sommets sont blancs */
	for(i=0;i<(g->nbN);i++)
	{
		chemin = (Noeud**) malloc (2*sizeof(Noeud*));
		chemin[0] = &(g->noeuds[i]);
		chemin[1] = NULL;
		Sommets[i] = nouvelleArete(chemin,2,infini);
	}

	/* On noircit le sommet de départ */
	setLongueurArete(&Sommets[n1],0);
	setPoidsArete(&Sommets[n1],0);

	nbBlancs = (g->nbN)-1;
	nbGris = 0;
	nbNoirs = 1;

	/* On grise ses successeurs */
	for(i=0;i<(g->nbN);i++)
	{
		if ((getLongueurArete(&Sommets[i]) == 2) && (i != n1))
		{
			a = getAreteNoeuds(g,n1,i);
			if (getLongueurArete(&a) == 2)
			{
				setLongueurArete(&Sommets[i],1);
				setPoidsArete(&Sommets[i],getPoidsArete(&a));
				setCheminIArete(&Sommets[i],getCheminIArete(&Sommets[n1],0),1);
				nbBlancs--;
				nbGris++;
			}
		}
	}


	/* BOUCLE PRINCIPALE */
	while(getLongueurArete(&Sommets[n2]) != 0)
	{
		/* Sélection du gris minimum */
		pmin = infini;
		for(i=0;i<(g->nbN);i++)
		{
			if (getLongueurArete(&Sommets[i]) == 1)
			{
				if (getPoidsArete(&Sommets[i]) < pmin)
				{
					pmin = getPoidsArete(&Sommets[i]);
					grismin = i;
				}
			}
		}

		/* S'il n'existe pas, c'est que le PCC non plus */
		if(pmin == infini)
		{
			printf("\nERREUR\nRecherche du plus court chemin entre des villes");
			printf(" situées dans des composantes connexes differentes. Abandon.\n");
			exit(EXIT_FAILURE);
		}

		/* (Ré)évaluation et grisage de ses successeurs */
		for(i=0;i<(g->nbN);i++)
		{
			if (i != grismin)
			{
				if (getLongueurArete(&Sommets[i]) == 1)
				{
					a = getAreteNoeuds(g,grismin,i);
					if (getLongueurArete(&a) == 2)
					{
						if ((getPoidsArete(&Sommets[grismin])+getPoidsArete(&a)) < getPoidsArete(&Sommets[i]))
						{
							setPoidsArete(&Sommets[i],getPoidsArete(&Sommets[grismin])+getPoidsArete(&a));
							setCheminIArete(&Sommets[i],getCheminIArete(&Sommets[grismin],0),1);
						}
					}
				}
				else if (getLongueurArete(&Sommets[i]) == 2)
				{
					a = getAreteNoeuds(g,grismin,i);
					if (getLongueurArete(&a) == 2)
					{
						setLongueurArete(&Sommets[i],1);
						setPoidsArete(&Sommets[i],getPoidsArete(&Sommets[grismin])+getPoidsArete(&a));
						setCheminIArete(&Sommets[i],getCheminIArete(&Sommets[grismin],0),1);
						nbBlancs--;
						nbGris++;
					}
				}
			}
		}

		/* Noircissage */
		setLongueurArete(&Sommets[grismin],0);
		nbNoirs++;
		nbGris--;
	}


	/* CONSTRUCTION DE L'ARETE RES A RETOURNER */
	chemin = (Noeud**) malloc ((g->nbN)*sizeof(Noeud*));
	chemin[0] = getCheminIArete(&Sommets[n2],0);
	pred = getCheminIArete(&Sommets[n2],1);
	lg = 1;
	while(pred != NULL)
	{
		chemin[lg] = pred;
		
		i=0;
		while (getCheminIArete(&Sommets[i],0) != pred)
		{ i++; }
		pred = getCheminIArete(&Sommets[i],1);

		lg++;
	}

	res.chemin = (Noeud**) malloc (lg*sizeof(Noeud*));
	for (i=0;i<lg;i++)
	{
		res.chemin[i] = chemin[lg-i-1];
	}
	
	res.longueur = lg;

	res.poids = getPoidsArete(&Sommets[n2]);


	/* LIBERATIONS */
	free(chemin);
	for(i=0;i<(g->nbN);i++)
	{
		testamentArete(&Sommets[i]);
	}
	free(Sommets);


	return res;
}


void completerPCC(Graphe* g)
{
	int i, j, k, l;
	Arete ainit, afin;

	for(i=0;i<(g->nbI);i++)
	{
		for(j=i+1;j<(g->nbI);j++)
		{
			k = getIndiceImportant(g,i);
			l = getIndiceImportant(g,j);
			ainit = getAreteNoeuds(g,k,l);
			if (getLongueurArete(&ainit) == 0)
			{
				afin = PCC(g,k,l);
				setAreteNoeuds(g,k,l,afin);
			}
		}
	}
}


/* Trie le tableau d'Aretes tableau, de longueur longueur */
/* Sert à kruskal */
static void triAretes(Arete* tableau, int longueur)
{
	int i,j;
	Arete a;

	for(i=1;i<longueur;i++) 
	{ 
		for(j=0;j<longueur-1;j++) 
		{ 
			if(getPoidsArete(&tableau[j])>getPoidsArete(&tableau[j+1])) 
			{ 
				a = tableau[j+1];
				tableau[j+1] = tableau[j]; 
				tableau[j] = a; 
			}
		}
	}
}


/* Algorithme de Kruskal */
Arete* kruskal(const Graphe* g, int* longsol)
{
	/* VARIABLES */
	int i, j, nbInduit, curseur, chefn1, chefn2;
	Arete* poidsinduits; /* liste des arêtes du graphe induit*/
	Arete* arbre; /* arbre solution */
	Noeud *n1, *n2;

	nbInduit = ((g->nbI)*(g->nbI-1)/2);
	curseur = 0;

	poidsinduits = (Arete*) malloc ((nbInduit)*sizeof(Arete)); 
	arbre = (Arete*) malloc ((nbInduit)*sizeof(Arete));

	/* CONSTRUCTION DU GRAPHE INDUIT + TRI DES ARETES */
	for(i=0;i<(g->nbI);i++)
	{
		for(j=i+1;j<(g->nbI);j++)
		{
			poidsinduits[curseur] = getAreteNoeuds(g, getIndiceImportant(g,i), getIndiceImportant(g,j));
			curseur++;
		}
	}

	triAretes(poidsinduits, nbInduit);


	curseur = 0;

	/* CONSTRUCTION DE L'ARBRE COUVRANT DE POIDS MINIMUM */
	/* On parcourt les arêtes du graphe induit */
	for(i=0;i<nbInduit;i++)
	{
		n1 = getCheminIArete(&poidsinduits[i],0);
		n2 = getCheminIArete(&poidsinduits[i],getLongueurArete(&poidsinduits[i])-1);
		chefn1 = getChefNoeud(n1);
		chefn2 = getChefNoeud(n2);

		/* On ajoute l'arête si elle ne créée pas de cycle dans arbre */
		if (chefn1 != chefn2)
		{
			arbre[curseur] = poidsinduits[i];
			curseur ++;
			/* Mise à jour des chefs */
			for(j=0;j<(g->nbI);j++)
			{
				if (getChefNoeud(g->importants[j]) == chefn2)
				{
					setChefNoeud(g->importants[j],chefn1);
				}
			}
		}
	}

	free(poidsinduits);

	*longsol = curseur;
	return arbre;
}


/* Algorithme de Kruskal (adapté pour les plus courts chemins) */
Arete* kruskal2(const Graphe* g, int* longsol)
{
	/* VARIABLES */
	int i, j, k, l, nbInduit, nbInduit2, curseur, chefn1, chefn2, imin, pmin, boolean;
	Arete* poidsinduits; /* liste des arêtes du graphe induit */
	Arete* arbre; /* arbre solution */
	Arete a, b;
	Noeud *n1, *n2;


	/* INITIALISATIONS */
	nbInduit = ((g->nbI)*(g->nbI-1)/2);
	nbInduit2 = nbInduit;
	curseur = 0;

	poidsinduits = (Arete*) malloc ((nbInduit)*sizeof(Arete));
	arbre = (Arete*) malloc ((nbInduit)*sizeof(Arete)); /*borne mieux ? (arbre) */


	/* CONSTRUCTION DU GRAPHE INDUIT */
	k=0;
	for(i=0;i<(g->nbI);i++)
	{
		for(j=i+1;j<(g->nbI);j++)
		{
			poidsinduits[k] = getAreteNoeuds(g, getIndiceImportant(g,i), getIndiceImportant(g,j));
			k++;
		}
	}

	
	/* CONSTRUCTION DE L'ARBRE COUVRANT DE POIDS MINIMUM */
	/* On répète l'opération pour chaque arête du graphe induit */
	for(j=0;j<nbInduit;j++)
	{
		/* Obtention de l'arête de poids minimum (on ne trie pas au préalable) */
		imin = 0;
		pmin = getPoidsArete(&poidsinduits[imin]);
		for(i=1;i<nbInduit2;i++)
		{
			if (getPoidsArete(&poidsinduits[i]) < pmin)
			{
				imin = i;
				pmin = getPoidsArete(&poidsinduits[imin]);
			}
		}


		/* Ajout de chacune des sous-arêtes de cette de poids minimum, si celle-ci ne crée pas de cycle */
		n1 = getCheminIArete(&poidsinduits[imin],0);
		n2 = getCheminIArete(&poidsinduits[imin],getLongueurArete(&poidsinduits[imin])-1);
		chefn1 = getChefNoeud(n1);
		chefn2 = getChefNoeud(n2);


		if (chefn1 != chefn2)
		{
		/* On parcourt le chemin composant l'arete */
			for (k=1;k<getLongueurArete(&poidsinduits[imin]);k++) 
			{
				a = getAreteNoeuds(g,(int)(getCheminIArete(&poidsinduits[imin],k-1)-(g->noeuds)),
								   (int)(getCheminIArete(&poidsinduits[imin],k)-(g->noeuds)));

				/* On vérifie que a n'est pas déjà dans l'arbre ! */
				boolean = 0;
				for (l=0;l<curseur;l++)
				{
					boolean += testEgalesAretes(&a,&arbre[l]);
				}

				if (boolean == 0)	
				{
					/* On ajoute a dans arbre */
					arbre[curseur] = a;
					curseur++;

					/* On met à jour les chefs */
					for (l=0;l<g->nbN;l++)
					{
						n2 = getCheminIArete(&a,1);
						chefn2 = getChefNoeud(n2);
						if (getChefNoeud(&((g->noeuds)[l])) == chefn2)
						{
							setChefNoeud(&((g->noeuds)[l]),chefn1);
						}
					}

					/* On met à jour les poids */
					for (l=1;l<nbInduit2;l++)
					{
						for(i=1;i<getLongueurArete(&poidsinduits[l]);i++)
						{
							b = getAreteNoeuds(g,(int)(getCheminIArete(&poidsinduits[l],i-1)-(g->noeuds)),
											   (int)(getCheminIArete(&poidsinduits[l],i)-(g->noeuds)));
							if (testEgalesAretes(&a,&b) == 1)
							{
								setPoidsArete(&poidsinduits[l],getPoidsArete(&poidsinduits[l])-getPoidsArete(&a));
							}
						}
					}

				}
			}
		}

		/* Reste à supprimer l'arête traitée de poidsinduits */
		nbInduit2--;
		for(i=imin;i<nbInduit2;i++)  
		{
			poidsinduits[i] = poidsinduits[i+1];
		}

	}
	
	
	free(poidsinduits);

	*longsol = curseur;
	return arbre;
}


void affichageGrapheTexte(const Graphe* g)
{
	int i, j;
	char nomville[50];
	Noeud n;
	Arete a;

	printf("nbN = %d\nnbI = %d\nnbP = %d\n", g->nbN, g->nbI, g->nbP);

	n = (g->noeuds)[0];
	getNomNoeud(&n,nomville);
	if (strcmp(nomville,"") != 0)
	{
		printf("\nVILLES\n");
		for (i=0;i<(g->nbN);i++)
		{
			n = (g->noeuds)[i];
			getNomNoeud(&n,nomville);
			printf("%s aux coordonnees %d,%d\n", nomville, getPosXNoeud(&n), getPosYNoeud(&n));
		}
	}

	printf("\nROUTES\n");

	for(i=0;i<(g->nbN);i++)
	{
			for(j=i+1;j<(g->nbN);j++)
			{
				a = getAreteNoeuds(g,i,j);
				if (getLongueurArete(&a) == 2)
				{ printf("Entre %d et %d : poids %d\n", i, j, getPoidsArete(&a)); }
			}
	}
	printf("\n");
	for(i=0;i<(g->nbN);i++)
	{
			for(j=i+1;j<(g->nbN);j++)
			{
				a = getAreteNoeuds(g,i,j);
				if (getLongueurArete(&a) > 2)
				{ printf("Entre %d et %d : longueur %d, poids %d\n", i, j, getLongueurArete(&a), getPoidsArete(&a)); }
			}
	}
}


void affichageSolutionTexte(const Graphe* g, const Arete* tab, const int longueur)
{
	int i, cout;
	Arete a;
	Noeud n;
	char nomville[50];

	cout = 0;
	printf("\nSOLUTION PROPOSEE\n");
	printf("Renovation de %d routes :\n", longueur);

	a = tab[0];
	n = *getCheminIArete(&a,0);
	getNomNoeud(&n,nomville);
	if (strcmp(nomville,"") == 0)
	{
		for (i=0;i<longueur;i++)
		{
			a = tab[i];
			printf("\n# Route entre les villes %d", ((int) (getCheminIArete(&a,0)-(g->noeuds))) + 1);
			printf(" et %d.\n", ((int) (getCheminIArete(&a,1)-(g->noeuds)) + 1));
			printf("  Cout de la renovation : %d\n", getPoidsArete(&a));
			cout += getPoidsArete(&a);
		}
	}
	else
	{
		for (i=0;i<longueur;i++)
		{
			a = tab[i];
			getNomNoeud(getCheminIArete(&a,0),nomville);
			printf("\n# Route entre les villes %d (%s)", (int) (getCheminIArete(&a,0)-(g->noeuds)), nomville);
			getNomNoeud(getCheminIArete(&a,1),nomville);
			printf(" et %d (%s),\n", (int) (getCheminIArete(&a,1)-(g->noeuds)), nomville);
			printf("  Cout de la renovation : %d\n", getPoidsArete(&a));
			cout += getPoidsArete(&a);
		}
	}

	printf("\n--- Cout total des travaux : %d ---\n",cout);
}



int testGraphe()
{
	Graphe g;
	Arete* tabsolution;
	int longsolution;

	printf("\nTEST DU MODULE GRAPHE\n");


	printf("\nTest du type de graphe \"1\"\n");

	printf("Initialisation...\n");
	g = nouveauGrapheFichier1("test/test1.txt");
	affichageGrapheTexte(&g);
	printf("Completion (PCC)...\n");
	completerPCC(&g);
	affichageGrapheTexte(&g);
	printf("Kruskal...\n");
	tabsolution = kruskal2(&g,&longsolution);
	affichageGrapheTexte(&g);
	affichageSolutionTexte(&g,tabsolution,longsolution);
	testamentGraphe(&g);
	free(tabsolution);
	printf("OK\n");

	printf("\nTest du type de graphe \"2\"\n");

	printf("Initialisation...\n");
	g = nouveauGrapheFichier2("test/test2.txt");
	affichageGrapheTexte(&g);
	printf("Completion (Euclide)...\n");
	completerEuclide(&g);
	affichageGrapheTexte(&g);
	printf("Kruskal...\n");
	tabsolution = kruskal(&g,&longsolution);
	affichageGrapheTexte(&g);
	affichageSolutionTexte(&g,tabsolution,longsolution);
	testamentGraphe(&g);
	free(tabsolution);
	printf("OK\n");

	printf("Initialisation...\n");
	g = nouveauGrapheFichier2("test/test2.txt");
	affichageGrapheTexte(&g);
	printf("Completion (PCC)...\n");
	completerPCC(&g);
	affichageGrapheTexte(&g);
	printf("Kruskal...\n");
	tabsolution = kruskal2(&g,&longsolution);
	affichageGrapheTexte(&g);
	affichageSolutionTexte(&g,tabsolution,longsolution);
	testamentGraphe(&g);
	free(tabsolution);
	printf("OK\n");

	printf("\nLe test est un succes.\n");
	return 0;
}


